package com.shawn.algorithm.dynamicprogramming;

/**
 * 0-1 背包问题
 */
public class ZeroOneBag {

	private int maxW = Integer.MIN_VALUE;
	/**
	 * 物品重量
	 */
	private int[] weight = {2, 2, 4, 6, 3};

	/**
	 * 物品数量
	 */
	private int n = 5;

	/**
	 * 背包最大承受重量
	 */
	private int w = 9;

	/**
	 * @param weight: 物品重量
	 * @param n：物品个数
	 * @param w：背包可承受重量
	 *
	 * @return
	 */
	public int knapsack(int[] weight, int n, int w) {
		boolean[][] states = new boolean[n][w + 1];
		states[0][0] = false;
		if (weight[0] <= w) {
			states[0][weight[0]] = true;
		}
		// 动态规划状态转移方程
		for (int i = 0; i < n; i++) {
			// 不把第i个物品放入背包
			for (int j = 0; j <= w; j++) {
				if (states[i - 1][j]) {
					states[i][j] = states[i - 1][j];
				}
			}
			// 把第i个物品放入背包
			for (int j = 0; j <= w - weight[i]; j++) {
				if (states[i - 1][j]) {
					states[i][j + weight[i]] = true;
				}
			}
		}
		for (int i = w; i >= 0; i--) {
			if (states[n - 1][i]) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * @param weight: 物品重量
	 * @param n：物品个数
	 * @param w：背包可承受重量
	 *
	 * @return
	 */
	public int knapsack2(int[] weight, int n, int w) {
		boolean[] states = new boolean[w + 1];
		states[0] = true;
		if (weight[0] <= w) {
			states[weight[0]] = true;
		}
		for (int i = 1; i < n; i++) {
			for (int j = w - weight[i]; j >= 0; j--) {
				if (states[j]) {
					states[j + weight[i]] = true;
				}
			}
		}
		for (int i = w; i >= 0; i--) {
			if(states[i]){
				return i;
			}
		}
		return -1;
	}


}
